package 约瑟夫问题;
/*Josephu问题为：设编号为  1，2，… n的 n个人围坐一圈，
 * 约定编号为 k（1<=k<=n）的人从 1开始报数，数到  m的那个人出列，
 * 它的下一位又从 1开始报数，数到 m的那个人又出列，依次类推，
 * 直到所有人出列为止，由  此产生一个出队编号的序列。*/
public class 约瑟夫问题 {
	public static void main(String[] args) {
		
		CircleLinkList list = new CircleLinkList();
		list.addLinkNode(5);
//		list.showList();
		
		list.outCircle(1, 2);
	}
}



//定义单向环形链表
class CircleLinkList{
	
	//第一位置，辅助指针
	private LinkNode first;
	
	public CircleLinkList() {
		first = new LinkNode();
		first.next = null;
	}
	
	
	//添加结点，构成环形链表 num 表示多少人
	public void addLinkNode(int num) {
		
		//校验
		if(num < 1) {
			System.out.println("输入不正确！");
			return;
		}
		
		//first 只是记录链表开头，不做其他用处
		
		//辅助指针，跟随新结点而动，帮助创建环形链表
		LinkNode p = new LinkNode();
		
		//添加结点，i 从 1 开始
		for(int i = 1; i <= num; i++) {
			//每一个 人/结点 ， 从 --------1 ----------开始编号
			LinkNode node = new LinkNode(i);
			
			//如果是第一个人，记录下来，并构成环形链表，并设置 p 辅助指针开始创建链表
			
			//--------------也不一定i = 1 只是 i的第一个数------------
			if(i == 1) {
				first = node;
				first.next = node;
				//使辅助指针进入链表创建过程
				p = first;
			}else {
				//不是第一个，就用 p 创建环形链表
				p.next = node;
				node.next = first;
				
				//移动 p 到最后一个结点，帮助链表创建下一个结点
				p = node;
			}
		}
	}
	
	
	
	//出圈
	/**
	 * 
	 * @param start start位置开始报数
	 * @param n 每次报 n 个数
	 */
	public void outCircle(int start,int n) {
		//从 start 位置开始数，数到 n 的出圈，然后从下一个重新开始数
		//不考虑输入参数错误问题，比如 start 超出链长
		
		//创建 p 辅助指针，始终在 报数的人 前一位，帮助记录 和 出圈
		//初始时，p 在链表最后一位，first在第一位
		LinkNode p = first;
		while(p.next != first) {
			p = p.next;
		}
		
		//将 p 和 first 移动到开始位置 ，一般都是 从 1 开始
		for (int i = 0; i < start-1; i++) {
			first = first.next;
			p = p.next;
		}
		
		//开始报数
		while(true) {
			
			//first 开始移动，表示当前报数的那个人
			for (int i = 0; i < n-1; i++) {
				first = first.next;
				p = p.next;
			}
			System.out.println(first.no + " 出圈。");
			//出圈
			first = first.next;
			p.next = first;
			
			if(first == p) {
				break;
			}
			
		}
		System.out.println(first.no + " 出圈。");
		
	}
	
	
	
	
	
	//遍历链表
	public void showList() {
		
		if(first == null) {
			System.out.println("链表空！");
			return;
		}
		
		LinkNode p = first;
		while(true) {
			//first 是第一个结点，不存在头结点，所以先输出，再判断
			System.out.println(p.no);
			if(p.next == first) {
				break;
			}
			p = p.next;
		}
	}
}



//定义结点 Boy
class LinkNode{
	public int no;
	public LinkNode next;
	
	public LinkNode() {
		super();
	}

	public LinkNode(int no) {
		super();
		this.no = no;
	}
}